The present invention is a system for providing three-dimensional computer graphics. More particularly, the present invention is a system that accelerates the processing of volume data for real-time ray casting of a three-dimensional image and a method thereof.
Volume rendering projects a volume dataset onto a two-dimensional (2D) image plane or frame-buffer. Volume rendering can be used to view and analyze three-dimensional (3D) data from various disciplines, such as biomedicine, geo-physics, computational fluid dynamics, finite element models and computerized chemistry. Volume rendering is also useful in the application of 3D graphics, such as Virtual Reality (VR), Computer Aided Design (CAD), computer games, computer graphics special effects and the like. The various applications, however, may use a variety of terms, such as 3D datasets, 3D images, volume images, stacks of 2D images and the like, to describe volume datasets.
As schematically depicted in FIG. 1, a volume dataset is typically organized as a 3D array of samples which are often referred to as volume elements or voxels. The volume dataset can vary in size, for example from 1283 to 10243 samples, and may also be non-symmetric, i.e., 512xc3x97512xc3x97128. The samples or voxels can also vary in size. For example, a voxel can be any useful number of bits, for instance 8 bits, 16 bits, 24 bits, 32 bits or larger, and the like.
The volume dataset can be thought of as planes of voxels or slices. Each slice is composed of rows or columns of voxels or beams. As depicted in FIG. 1, the voxels are uniform in size and regularly spaced on a rectilinear grid. Volume datasets can also be classified into non-rectilinear grids, for example curvilinear grids. These other types of grids can be mapped onto regular grids.
Voxels may also represent various physical characteristics, such as density, temperature, velocity, pressure and color. Measurements, such as area and volume, can be extracted from the volume datasets. A volume dataset may often contain more than a hundred million voxels thereby requiring a large amount of storage. Because of the vast amount of information contained in a dataset, interactive volume rendering or real-time volume rendering defined below requires a large amount of memory bandwidth and computational throughput. These requirements often exceed the performance provided by typical modern workstations and personal computers.
Volume rendering techniques include direct and indirect volume rendering. Direct volume rendering projects the entire dataset onto an image-plane or frame buffer. Indirect volume rendering extracts surfaces from the dataset in an intermediate step, and these projected surfaces are approximated by triangles and rendered using the conventional graphics hardware. Indirect volume rendering, however, only allows a viewer to observe a limited number of values in the dataset (typically 1-2) as compared to or all of the data values contained therein for direct volume rendering.
Direct volume rendering that is implemented in software, however, is typically very slow because of the vast amount of data to be processed. Moreover, real-time direct (interactive) volume rendering (RTDVR) involves rendering the entire dataset at over 10 Hz, however, 30 Hz or higher is desirable. Recently, RTDVR architectures have become available for the personal computer, such as VolumePro, which is commercially available from RTVIZ, a subsidiary of Mitsubishi Electronic Research Laboratory. VIZARD II and VG-Engine are two other RTDVR accelerators that are anticipated to be commercially available. These accelerators may lower the cost of interactive RTDVR and increase performance over previous non-custom solutions. Moreover, they are designed for use in personal computers. Previous solutions for real-time volume rendering used multi-processor, massively parallel computers or texture mapping hardware. These solutions are typically expensive and not widely available due to, for instance, the requirement for parallel computers. Alternatively, these solutions generate lower quality images by using texture-mapping techniques.
Although accelerators have increased the availability and performance of volume rendering, a truly general-purpose RTDVR accelerator has yet to emerge. Current accelerators generally support parallel projections and have little or no support for perspective projections and stereoscopic rendering. These different projections are illustrated in FIG. 2. Stereoscopic rendering is a special case where two images, generally two perspective images, are generated to approximate the view from each eye of an observer. Stereoscopic rendering typically doubles the amount of data to be processed to render a stereoscopic image. Moreover, current accelerators also require high memory bandwidths that can often exceed 1 Gbyte per second for a 2563 dataset.
Furthermore, these current accelerators are typically either image-order or object-order architectures. An image-order architecture is characterized by a regular stepping through image space and the object-order architecture is characterized by a regular stepping through object space. Image-order ray casting architectures may support algorithmic speed-ups, such as space leaping and early ray termination, and perspective projections. Object-order architectures tend to provide more hardware acceleration and increased scalability. Object-order architectures, however, have not generally provided algorithmic acceleration. The trade-off between these various limitations are typically either (i) good parallel rendering performance and no support for perspective projections or (ii) good algorithmic acceleration and little hardware acceleration and vice versa.
The voxel-to-pipeline topologies of typical image-order and object-order accelerators are shown schematically in FIGS. 3 and 4, respectively. Image-order architectures must access several voxels from a volume memory per processor. This typically causes a bottleneck in achievable hardware acceleration and thereby limits the number of useful processors. For example, as illustrated in FIG. 3, a typical image-order architecture has an 8-to-1 bottleneck for each image-order pipeline. Although algorithmic acceleration for the reconstruction, classification, shading and the composition of the voxels can often increase performance, such an increase in performance is often outweighed by the voxel bottleneck in the memory system, thereby limiting the overall acceleration.
As depicted in FIG. 4, object-order pipelines generally require only one voxel access per processor thereby providing greater hardware acceleration due to the lack of a voxel or a memory bottleneck. Object-order reconstruction of the dataset, however, makes it difficult, if not impossible, to implement algorithmic acceleration or support perspective projections.
Neither image-order nor object-order architectures are general-purpose techniques because of their limitations. For example, image-order architectures only deliver interactive performance for certain types of datasets by relying heavily on algorithmic acceleration. Performance can be extremely sensitive to viewing parameters (and dataset characteristics) potentially causing large fluctuations in performance. On the other hand, object-order architectures yield more consistent performance but typically do not support perspective projections. As a result, these architectures cannot be used for applications that require stereoscopic rendering, virtual reality, computer graphics, computer games and fly-throughs.
Thus, there is a need for a device capable of general-purpose volume rendering performance that supports interactive rendering for both parallel and perspective projections. Furthermore, there is a need for a general-purpose device that supports interactive rendering for stereoscopic displays.
The present invention is a general-purpose device that supports interactive rendering for parallel and perspective projections and stereoscopic rendering thereof. The general-purpose device is further characterized as a digital electronic system for real-time volume rendering of a 3D volume dataset. A new hybrid ray casting is used to volume render a real-time image from external memory. Volume rendering includes reconstruction, classification, shading and composition of subvolumes or voxels of a volume dataset representing the 3D image. Early ray termination and space leaping accelerate the processing of the voxels by dynamically reducing the number of voxels necessary to render the image. Furthermore, the underlying hardware of the present invention processes the remaining voxels to in an efficient manner. This allows for real-time volume imaging for stereoscopic displays.
The hardware architecture of the present invention supports projection-guided ray casting, early ray termination and space leaping for improved memory usage. The hardware architecture further accelerates the volume rendering due, in part, to regular and predictable memory accessing, fully pipelined processing and space leaping and buffering of voxels to eliminate voxel-refetch.
The incorporation of the projection guided ray casting, including early ray termination and space leaping, and the hardware architecture permit rendering of the image where the rendering is not the critical time-consuming operation. In other words, the present invention can render many volumes in a faster time period than the entire volumes can be read from external memory.
Another aspect of the present invention includes a method for volume rendering an image where there is no substantial refetching of data from external memory. Perspective projections, under certain circumstances, may require a minimal, but non-limiting, refetching of some data. The method includes early ray termination and space leaping accelerations and the processing of voxels in predictable manner in hardware to volume render an image in real-time.